# encoding=utf-8
'''
Created on Nov 21, 2012

@author: junior
'''
from search import Node
from utils import FIFOQueue, Stack
import re
class TreeSearch(Node):

	def __init__(self, problem, frontier, limit='Inf'):

		self._problem = problem
		self._frontier = frontier
		self._limit = limit

	def execute(self):

		"""A fim de ter uma saída compatível com o escolhido para o formato de saída do grafo ou árvore
		e a quantidade de nós extendidos durante a procura dependendo se essa função recebe uma fila (FIFOQueue) ou uma pilha
		(Stack) realiza a procura em largura ou a procura em profundidade em uma árvore"""

		# Lista que tem o formato [[A,[B,C],[D,[E,F]]] onde cada lista interna é um nó e uma lista de
		# nós expandidos
		tree = []

		# Lista que armazena os nós já visitados (ela será usada para verificar se um nó já existe na
		# árvore para posteriormente dentro da função renomeá-la (exemplo: se já existe A, precisa ser renomeada
		# para A1) a fim de ter uma saída em uma árvore; a biblioteca que mostra graficamente a árvore funciona
		# só para grafos onde os nós não podem repetir
		visitados = []

		# Esta lista contém os nós que foram expandidos e tem a função de verificar se os nós já existem
		# na árvore para posteriormente dentro da função renomeá-la a fim de ter uma saída em uma árvore
		# a biblioteca que mostra graficamente a árvore funciona só para grafos onde os nós não podem
		# repetir
		if isinstance(self._frontier, FIFOQueue):
			fronteira_tree = FIFOQueue()
		else:
			fronteira_tree = Stack()

		# Adiciona na fronteira o nó inicial para a procura e para o grafo
		self._frontier.append(Node(self._problem.initial))
		fronteira_tree.append(self._problem.initial)

		# Armazena a quantidade de nós extendidos
		extendidos = 0
		explored = set()
		# Aqui começa a procura
		# um limite para a busca
		if self._limit != 'Inf' and isinstance(self._frontier, list):
			limit = 0

		while self._frontier:

			# Retiramos um nó da fronteira (uma pilha ou fila)
			node = self._frontier.pop()

			# Repetimos o mesmo processo nas listas para manipular os nós que vão fazer parte do grafo
			noh = fronteira_tree.pop()


			if self._problem.goal_test(node.state):
				# adiciona o nó ao grafo e uma lista vazia para ele aparecer na janela
				tree.append([noh, []])
				return node, tree, extendidos  # e retorna o nó com a solução, a árvore que foi construída e o número
				# de nós que foram extendidos
			explored.add(noh)

			if self._limit != 'Inf' and isinstance(self._frontier, list):
				if limit > self._limit:
					return node, tree, extendidos

			# O nó é expandido nos subnós e são adicionados à fronteira
			nosASeremAdicionados = node.expand(self._problem)
			self._frontier.extend(nosASeremAdicionados)

			# adicionamos mais um nó aos extendidos
			extendidos += 1

			# lista temporária vazia para armazenar os subnós do nó explorado (para a árvore)
			subnohs_temp = []

			# Neste loop é verificado cada um dos subnós e se ele já estiver na árvore ele é
			# renomeado em uma sequência: se A existe ele é renomeado para A1
			for subnoh in nosASeremAdicionados:
				if (subnoh.state not in fronteira_tree) and (subnoh.state not in explored):
					subnohs_temp.append(subnoh.state)
					explored.add(subnoh.state)
				else:
					explored_temp = list(explored)

					for i in range(len(explored_temp)):
						if subnoh.state in explored_temp[i]:
							explored_temp[i] = re.sub('\D', '', explored_temp[i])
							if explored_temp[i] == '':
								explored_temp[i] = 0
							else:
								explored_temp[i] = int(explored_temp[i])
						else:
							explored_temp[i] = 0

					explored_temp[:] = (value for value in explored_temp if value != 0)

					pos = sorted(explored_temp)[-1] if len(explored_temp) != 0 else 0
#					if pos==None or filter(lambda  x:x.isdigit(),(sorted(explored))[pos])=='':
#						ultimo_numero=0
#					else:
#						ultimo_numero=int(filter(lambda  x:x.isdigit(),(sorted(explored))[pos]))
					proximo_numero = pos + 1
					visitados.append(subnoh.state + str(proximo_numero))
					subnohs_temp.append(subnoh.state + str(proximo_numero))
					explored.add(subnoh.state + str(proximo_numero))

			# Depois da verificação dos nós adicionamos a lista [nó,[lista_de_subnós]] à árvore
			fronteira_tree.extend(subnohs_temp)
			tree.append([noh, subnohs_temp])

			if self._limit != 'Inf' and isinstance(self._frontier, list):
				limit += 1

		return None, tree, extendidos  # Se não houver solução

